Steve Bono

November 25, 2002

CIS 203, Artificial Intelligence

Professor Wang

Fuzzy Traffic Control Signals (Draft 02)

Fuzzy Logic is a difficult concept for most to grasp. Even mathematicians are sometimes perplexed by its odd sense of composition. Too often, fuzzy logic relies on generalizations, "very", "some what", "slow", that mathematicians scoff at. How can something so seemingly imperfect yield such accurate results? The fact is, fuzzy logic and fuzzy set theory are based on a sound set of axioms, by which all of its theorems have been developed, as in any mathematical system. When a system becomes to complex to represent efficiently with any conventional mathematics, fuzzy logic is there to save the day.

One such system is traffic patterns. Though it would seem rather simple to represent an intersection mathematically, it turns out it is very complex and becomes increasingly more complex as additional lanes, directions and turning signals are incorporated into the system. To optimally control any one intersection or a series of intersections without constructing a detailed mathematical system, we turn to fuzzy logic for the answer.

Traffic signals are notoriously unintelligent. Most operate simply on timers, which is clearly the least optimal strategy in practice. Less frequently, traffic signals rely on sensors to determine if there are cars present in any one lane or direction. This approach is better, in that it will not waste as much time as the first type, but it is still in many ways inaccurate. When heavy volumes of traffic are traversing an intersection, the sensor method alone cannot accurately manage the traffic. A third type of traffic controller is human operated. This method is extremely expensive compared to a machine that could do the same work, but in contrast is much more accurate than either of the first types. Again, human error, boredom or many other factors could result in a human operator of a traffic control signal performing less than optimal.

A machine, operating with the same mindset so to speak, of a human operator, will not get bored, and if programmed correctly not poorly judge a situation. Accompanied by the appropriate sensors, an artificially intelligent traffic signal could manage the traffic flow of an intersection as optimally as possible.

Objectives:

1. Minimize the average waiting time of cars in all directions.

2. Uniformly distribute the average waiting time of cars in all directions.

Designing the Controller

In order to create a fuzzy logic controller to fulfill the given objectives, we must proceeded by following the following steps.

· Determine the inputs to the system.

· Determine the maximum and minimum values for each inputs.

· Determine the fuzzy sets representing the inputs.

· Determine the memberships of each value in their respective fuzzy sets.

· Determine the rule base by which to reason.

· Determine the additional rules for the rule base.

· Determine the methodology for reasoning.

· Determine the methods for defuzzification.

In order to examine an intersection, we must first describe the state of such an intersection. There are numerous combinations of different directions and different rules that affect the way in which traffic flows through an intersection. These combinations range from simple unidirectional intersections, to bi-directional or even more complex multi-directional intersections.

In order to understand the fundamental concepts of a fuzzy traffic control signal, I will first attempt to only simulate an intersection consisting of two directions of traffic, where only one of the directions may have right of passage at a time.

Determine the inputs

Note: The scope of this report is to examine the performance of a fuzzy logic controller, and not physically produce such a device. Therefore, all inputs and sensors to indicate the values are assumed to have been developed and implemented in the intersection being tested.

Input A: The average waiting time of cars behind the red signal.

Input B: The traffic density of the cars going through the green signal.

These input values can be obtained by placing sensors a predetermined distance from the intersection and in the intersection itself. Their purpose will be to count the number of cars entering the area between the two sensors and which have not yet gone through the intersection. Therefore, we can obtain the number of cars behind a red signal, as well as the times they have been waiting. The average time is simply the total of all waiting times for cars behind the red signal, divided by the number of waiting cars.

Similarly, the traffic density of the direction facing a green signal can be computed in number of cars per minute, by counting the number of cars entering and exiting the intersection in a given time frame. For instance, if 30 seconds have elapsed and 20 cars have traversed the intersection, then the vehicles per minute (VPM) will be

20 / (30 / 60) = 40 VPM

Determining the maximum and minimum possible input values

To accurately create fuzzy sets and a rule base in the steps to designing a fuzzy logic controller, it is necessary to set limitations on the inputs, or at least feasibility limitations, i.e. there will never be more than 120 VPM, or the waiting time of any car may never exceed 180 seconds. It would be ridiculous to consider a case where the number of vehicles traversing an intersection with in a minute would exceed the thousands, as would it be equally absurd to consider a case where the waiting time of a vehicle at a red signal span multiple hours.

For the sake of this simulation, I will consider only the case where the VPM is between 0 and 120 inclusive, and the average waiting time behind a red signal will span the range 0 to 180 with a three minute wait as the maximum. Any larger number of VPM or average wait would provide a level of danger that we are not considering in this experiment. A long wait may cause aggravated drivers to assume the signal is malfunctioning and ignore it.

Range of inputs:

Input A: [0, 1, ... 180]

Input B: [0, 1, ... 120]

Determining the fuzzy sets to represent the inputs

With any fuzzy logic controller, it is necessary to devise a system of fuzzy sets for which input values may hold a value in. That is, each crisp input value will hold a certain membership value within each fuzzy set.

Firstly, we must determine what these fuzzy sets are. For input A, the average wait will be described as very short, short, medium, long, very long, where each set's name is a description of the average waiting time. Input B's fuzzy sets will consist of very few, few, some, many, very many, and again each set's name subjectively represents the VPM for the intersection in the direction of the green signal.

Note that there are five sets for each input parameter. This has been chosen for the following reasons:

a) It provides a large enough quantity of rule possibilities without generating a rule base of monstrous proportions. For all intents and purposes, this rule base will be manageable.

In fact, the absolute maximum amount of rules which can be constructed from this set up is 5^2. That is, for each input argument, there are five rules, and for each possible value of input A, there are five possibilities for input B. Hence, 5^2.

Generally we can say that m fuzzy sets for each n inputs will provide a maximum of m^n rules in a rule base. (Yan 53).

b) The number of fuzzy sets chosen (5) is odd. This provides the distribution of the fuzzy sets over the input range with a middle ground. (Yan 53).

Fuzzy Sets

Input A: very short, short, medium, long, very long.

Input B: very few, few, some, many, very many.

Determining the memberships for each possible value of input

Determining the membership of each input value in each fuzzy set should be chosen carefully. Often, these membership functions are later refined after careful observation to provide optimal results. In some cases even, the system will itself adjust the membership values and actually learn on its own the best way to distribute the values.

Design principles to consider, offered by (Yen 48) include the following:

Principle 1:

That is, a fuzzy set must intersect with its two adjacent fuzzy sets, and may not intersect with any other sets in the spectrum.

Therefore, very few /\ few is not null, but very few intersected with any other set will provide the null set, and few will intersect with very few and some, but with no other set.

Principle 2:

Which translates in English as the sum of all x's membership functions over all fuzzy sets is 1, where is the value of x's membership in the set .

For example, if an input value x has a positive membership in the sets some, many and very many, and whose membership functions are 0.15, 0.65, 0.20, then the sum of x's membership over all fuzzy sets is 0 + 0 + 0.15 + 0.65 + 0.20 = 1.

Keeping in mind these principles I chose to create membership values as seen in figure 2. The distribution is symmetric for ease of computation and design and the membership functions are triangular again for ease of computation and design. Integer values for these membership functions are represented in table 3.

Determining the rule base

Since here are only two input arguments in this system, we can represent the rule base as a rule matrix where the rows represent membership in the fuzzy sets for the average wait, and the columns represent membership in a fuzzy sets for traffic density.

	Very Few	Few	Some	Many	Very Many
Very Short	?	?	?	?	?
Short	?	?	?	?	?
Medium	?	?	?	?	?
Long	?	?	?	?	?
Very Long	?	?	?	?	?

While determining the rule base, it is necessary to abstract what exactly should be done given each situation, long wait AND few VPM, etc..

Initially, I decided that a very long wait should be taken as a high priority to change and have indicated a change whenever the wait for the cars behind the red signal becomes "very long." Similarly, if there are very many cars, by stopping the traffic and switching the signal from green to red, it will cause a faster buildup of cars, which will immediately cause a long wait for the high traffic density direction, where as the currently waiting cars are still only at a wait of "long" and not yet "very long." Therefore, I chose to not change the light in the case that traffic density was "very many", except in the case where the opposing traffic has already been waiting "very long."

	Very Few	Few	Some	Many	Very Many
Very Short	?	?	?	?	NC
Short	?	?	?	?	NC
Medium	?	?	?	?	NC
Long	?	?	?	?	NC
Very Long	CH	CH	CH	CH	CH

Constructing the rest of the rule base is a little more intuitive, meaning that a higher traffic density, when placed behind a red signal, will endure a longer average waiting time. Therefore, in all cases for the rule base where the current average waiting time is shorter than the predicted average waiting time of the opposing traffic, the signal will not change.

	Very Few	Few	Some	Many	Very Many
Very Short	?	NC	NC	NC	NC
Short	CH	?	NC	NC	NC
Medium	CH	CH	?	NC	NC
Long	CH	CH	CH	?	NC
Very Long	CH	CH	CH	CH	CH

In the case where the waiting times will probably be the same, the signal does not change since the changing of the signal will most likely cause a delay during the deceleration of moving cars and acceleration of stopped vehicles. Therefore we conclude the completion of the rule base as:

	Very Few	Few	Some	Many	Very Many
Very Short	NC	NC	NC	NC	NC
Short	CH	NC	NC	NC	NC
Medium	CH	CH	NC	NC	NC
Long	CH	CH	CH	NC	NC
Very Long	CH	CH	CH	CH	CH

This can be translated as the following set of IF...THEN statements:

IF average wait is very short AND VPM is very few THEN no change

IF average wait is very short AND VPM is few THEN no change

IF average wait is very short AND VPM is some THEN no change

IF average wait is very short AND VPM is many THEN no change

IF average wait is very short AND VPM is very many THEN no change

IF average wait is short AND VPM is very few THEN change

IF average wait is short AND VPM is few THEN no change

IF average wait is short AND VPM is some THEN no change

IF average wait is short AND VPM is many THEN no change

IF average wait is short AND VPM is very many THEN no change

IF average wait is medium AND VPM is very few THEN change

IF average wait is medium AND VPM is few THEN change

IF average wait is medium AND VPM is some THEN no change

IF average wait is medium AND VPM is many THEN no change

IF average wait is medium AND VPM is very many THEN no change

IF average wait is long AND VPM is very few THEN change

IF average wait is long AND VPM is few THEN change

IF average wait is long AND VPM is some THEN change

IF average wait is long AND VPM is many THEN no change

IF average wait is long AND VPM is very many THEN no change

IF average wait is very long AND VPM is very few THEN change

IF average wait is very long AND VPM is few THEN change

IF average wait is very long AND VPM is some THEN change

IF average wait is very long AND VPM is many THEN change

IF average wait is very long AND VPM is very many THEN change

Determining additional rules

If the value of the input in two or more membership functions yields an equivalent rule to be followed we must define another set of rules.

Assume there are n rules produced which assume a change should be made, and m rules produced which consequent to no change.

Then, if n > m, execute a change, otherwise do not change the signal. This gives precedence to the opposing traffic behind an already green signal in the event of a tie.

Determining a methodology for reasoning

For this experiment, the MAX-MIN procedure will be adopted. Through this process, each input's membership function will be computed for each combination of input A and B. That is, we will compute the membership function of input A in all fuzzy sets representing the average wait and the membership function of input B in all fuzzy sets representing traffic density. In each case (or rule), the minimum membership value in the respective set between the two inputs in the antecedent of the rule will represent the value of the output consequent.

For example, if input A = x and input B = y, then min(very short(x), some(y)) will represent the value of the output for the rule IF average time is very short AND VPM is some. A clear representation of this method is represented in figure 4.

Determining the defuzzification process

Once the values for the set of inferred outputs have been calculated, we must take these results and produce a meaningful output value. Since there is no particular "fire strength" for this experiment, simply choose the maximum value(s) of all of the output actions produced by the fuzzy inference system. If their is a unique maximum, that output is to be carried out. If there are multiple equivalent outputs, the secondary rule set is used to determine the output to be carried out (see section on defining additional rules).

Designing the simulator

What exactly is the simulation?

The simulation consists primarily of a means for evaluating the fuzzy logic controller (FLC) described in the first portion of this report. It represents a discrete system, more precisely an intersection where the FLC is placed inside of a traffic control signal.

The program will simulate cars arriving and moving through an intersection as well as arriving and waiting at the intersection for the appropriate time to move. That is, the program will allow cars to travel through green signals, and force them to wait at red signals. Again, for the an initial attempt at a FLC for this purpose, the simulation will consist of only two directions, which cannot both be active at the same time. One direction must wait while vehicles in the other direction must proceed.

The simulation consists of an intersection (2 directions), cars arriving and departing the intersection, and a traffic signal which does not let the two directions be open simultaneously.

What are the states of the system?

Since this simulation in some ways represents a discrete system of events, it is helpful to determine what the states of the system are. Primarily there are only two states for the initial two direction simulation, direction 1 (d1) green - direction 2 (d2) red, and d1 red - d2 green.

These are the only states necessary for this simulation. Other possible states to consider are the states in between signal switching, i.e. a yellow light or delay between red and green light switching. However, this simulation does not consider such states.

What events change the state of the system?

In considering what changes the system state, note that the system is incremented by time. That is, the state of the system is reevaluated on a second by second basis. This duration can be changed for other purposes, but I will be testing with this value.

Each iteration of the system clock forces the system to reevaluate its state based on the average waiting time of cars behind the red signal and the traffic density for the direction facing a green signal. The FLC will determine if a change of state is warranted based on these input values.

How are the inputs for the FLC calculated?

To reiterate, the inputs for the FLC consist of average waiting time (input A) and traffic density (input B).

The average waiting time is calculated by summing the difference between the current time and the arrival time of each car, for all cars waiting at a red signal and then dividing by the total number of waiting cars.

For example, if the current system time is 500s (500 seconds have elapsed since the simulation has begun), and the waiting cars behind a red signal have arrival times 100s, 250s, and 350s, then the average is computed as follows:

( (500 - 100) + (500 - 250) + (500 - 350) ) / 3 s/car = 266.667s/car

Input B is calculated by keeping track of the total number of cars to traverse the intersection since the signal lasted changed from red to green and then dividing by the total time that has elapsed, and finally converting the value to VPM.

For example, if the current time is again 500s, and the signal changed from red to green at 400s and the number of cars to traverse the intersection since the last signal change is 35, then

VPM = 35 / ((500 - 400) / 60) = 21

How does the FLC infer an action?

The FLC infers action by the methods described in the first part of this report. It evaluates the respective membership values of the input arguments and computes the relative output argument strengths. If then a unique maximum value is found, it is returned, otherwise the secondary rules determine the output value to be returned.

How is the simulation to be used?

This simulation can be used to calculate various evaluation data from the running simulation. These results include:

maximum waiting time for any vehicle in both directions

maximum traffic density reached in both directions

overall average waiting time, and average waiting time for each direction

overall throughput of the intersection, and throughput in individual directions.

These results can then be compiled various data sets for the rule base and membership functions until an optimal data set is compiled.

It may be necessary to use completely different data sets for different situations of varying traffic density.